Hoàng Văn Toái sinh ngày 9 tháng 10 năm 1950 tại xã Xuân Giang, huyện Bắc Quang, tỉnh Hà Giang. Ông nhập ngũ từ tháng 7 năm 1968 và đến tháng 3 năm 1969 thì được kết nạp vào Đảng Cộng sản Việt Nam. Trong 4 năm đảm nhiệm vị trí Trung đoàn trưởng Trung đoàn 14 thuộc Sư đoàn 313, ông đã tham gia vào cuộc chiến biên giới tại Vị Xuyên vào năm 1984.[4][5] Về sau, ông dần lên đến vị trí Chỉ huy trưởng Bộ Chỉ huy quân sự tỉnh Hà Giang. Tháng 2 năm 2002, ông được bổ nhiệm làm Phó Tư lệnh Quân khu 2 và thăng hàm Thiếu tướng không lâu sau đó.[6][7] Đến năm 2007, ông trở thành Phó Tư lệnh Tham mưu trưởng của Quân khu 2 và giữ chức vụ này cho đến khi về hưu vào năm 2011.[8][9]